home *** CD-ROM | disk | FTP | other *** search
/ Sprite 1984 - 1993 / Sprite 1984 - 1993.iso / src / lib / c / stdlib / RCS / bsearch.c,v < prev    next >
Encoding:
Text File  |  1989-05-19  |  3.0 KB  |  177 lines
  1. head     1.4;
  2. branch   ;
  3. access   ;
  4. symbols  ;
  5. locks    ; strict;
  6. comment  @ * @;
  7.  
  8.  
  9. 1.4
  10. date     89.05.18.17.09.12;  author rab;  state Exp;
  11. branches ;
  12. next     1.3;
  13.  
  14. 1.3
  15. date     89.04.06.10.12.17;  author rab;  state Exp;
  16. branches ;
  17. next     1.2;
  18.  
  19. 1.2
  20. date     89.02.23.16.11.21;  author rab;  state Exp;
  21. branches ;
  22. next     1.1;
  23.  
  24. 1.1
  25. date     89.02.18.20.38.35;  author rab;  state Exp;
  26. branches ;
  27. next     ;
  28.  
  29.  
  30. desc
  31. @@
  32.  
  33.  
  34. 1.4
  35. log
  36. @*** empty log message ***
  37. @
  38. text
  39. @/* 
  40.  * bsearch.c --
  41.  *
  42.  *    Source code for the bsearch library routine.
  43.  *
  44.  * Copyright 1989 Regents of the University of California
  45.  * Permission to use, copy, modify, and distribute this
  46.  * software and its documentation for any purpose and without
  47.  * fee is hereby granted, provided that the above copyright
  48.  * notice appear in all copies.  The University of California
  49.  * makes no representations about the suitability of this
  50.  * software for any purpose.  It is provided "as is" without
  51.  * express or implied warranty.
  52.  */
  53.  
  54. #ifndef lint
  55. static char rcsid[] = "$Header: /sprite/src/lib/c/stdlib/RCS/bsearch.c,v 1.3 89/04/06 10:12:17 rab Exp Locker: rab $";
  56. #endif /* not lint */
  57.  
  58.  
  59. #include <stdlib.h>
  60.  
  61. #include <stdio.h>
  62. #include <sys/types.h>
  63.  
  64. #ifndef __STDC__
  65. #define const   /**/
  66. #endif
  67.  
  68.  
  69. /*
  70.  *----------------------------------------------------------------------
  71.  *
  72.  * bsearch --
  73.  *
  74.  *    Bsearch searches base[0] to base[n - 1] for an item that
  75.  *      matches *key.  The function cmp must return negative if its first
  76.  *      argument (the search key) is less that its second (a table entry),
  77.  *      zero if equal, and positive if greater.  Items in the array must
  78.  *      be in ascending order.  
  79.  *
  80.  * Results:
  81.  *    Returns a pointer to a matching item, or NULL if none exits.
  82.  *
  83.  * Side effects:
  84.  *    None.
  85.  *
  86.  *----------------------------------------------------------------------
  87.  */
  88.  
  89. char *
  90. bsearch(key, base, n, size, cmp)
  91.     const char *key;
  92.     const char *base;
  93.     size_t n;
  94.     size_t size;
  95. #ifdef __STDC__
  96.     int (*cmp)(const void *, const void *);
  97. #else
  98.     int (*cmp)();
  99. #endif
  100. {
  101.     const char *middle;
  102.     int c;
  103.  
  104.  
  105.     for (middle = base; n != 0;) {
  106.     middle += (n/2) * size;
  107.     if ((c = (*cmp)(key, middle)) > 0) {
  108.         n = (n/2) - ((n&1) == 0);
  109.         base = (middle += size);
  110.     } else if (c < 0) {
  111.         n /= 2;
  112.         middle = base;
  113.     } else {
  114.         return (char *) middle;
  115.     }
  116.     }
  117.     return NULL;
  118. }
  119.  
  120. @
  121.  
  122.  
  123. 1.3
  124. log
  125. @*** empty log message ***
  126. @
  127. text
  128. @d17 1
  129. a17 1
  130. static char rcsid[] = "$Header: /sprite/src/lib/c/stdlib/RCS/bsearch.c,v 1.2 89/02/23 16:11:21 rab Exp Locker: rab $";
  131. d53 2
  132. a54 2
  133.     const _Void *key;
  134.     const _Void *base;
  135. d76 1
  136. a76 1
  137.         return (_Void *) middle;
  138. @
  139.  
  140.  
  141. 1.2
  142. log
  143. @*** empty log message ***
  144. @
  145. text
  146. @d17 1
  147. a17 1
  148. static char rcsid[] = "$Header: /sprite/src/lib/c/stdlib/RCS/bsearch.c,v 1.1 89/02/18 20:38:35 rab Exp Locker: rab $";
  149. d26 1
  150. a26 4
  151. #ifdef __STDC__
  152. #define _Void void
  153. #else
  154. #define _Void char
  155. d51 1
  156. a51 1
  157. _Void *
  158. @
  159.  
  160.  
  161. 1.1
  162. log
  163. @Initial revision
  164. @
  165. text
  166. @d17 1
  167. a17 1
  168. static char rcsid[] = "$Header$";
  169. d69 2
  170. a70 4
  171.     middle = base;
  172.     for (;;) {
  173.     if (n == 0)
  174.         return NULL;
  175. d82 1
  176. @
  177.